|
In computational complexity theory, a gap reduction is a reduction to a particular type of decision problem, known as a ''c-gap problem''. Such reductions provide information about the hardness of approximating solutions to optimization problems. In short, a gap problem refers to one wherein the objective is to distinguish between cases where the best solution is above one threshold from cases where the best solution is below another threshold, such that the two thresholds have a gap in between. Gap reductions can be used to demonstrate inapproximability results, as if a problem may be approximated to a better factor than the size of gap, then the approximation algorithm can be used to solve the corresponding gap problem. ==c-gap problem== We define a c-gap problem as follows: given an optimization (maximization or minimization) problem P, the equivalent c-gap problem distinguishes between two cases, for an input k and an instance x of problem P: : . Here, the best solution to instance x of problem P has a cost, or score, below k. : . Here, the best solution to instance x of problem P has a cost above c⋅k. The gap between the two thresholds is thus c. Note that whenever OPT falls between the thresholds, there is no requirement on what the output should be. A valid algorithm for the c-gap problem may answer anything if OPT is in the middle of the gap. The value c does not need to be constant; it can depend on the size of the instance of P. Note that c-approximating the solution to an instance of P is at least as hard as solving the c-gap version of P. One can define an (a,b)-gap problem similarly. The difference is that the thresholds do not depend on the input; instead, the lower threshold is a and the upper threshold is b. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Gap reduction」の詳細全文を読む スポンサード リンク
|